class Solution:
    def maximumSwap(self, num: int) -> int:
        num = list(str(num))
        hash1 = [len(num)] * 10
        replaceIndex = (len(num)-1, len(num)-1)
        for i in range(len(num)):
            intI = int(num[i])
            for j in range(intI):
                if hash1[j] < replaceIndex[0]:
                    replaceIndex = (hash1[j], i)
                elif hash1[j]==replaceIndex[0]:
                    if intI>=int(num[replaceIndex[1]]):
                        replaceIndex = (hash1[j],i)
            hash1[intI] = min(hash1[intI], i)
        num[replaceIndex[0]],num[replaceIndex[1]]=num[replaceIndex[1]],num[replaceIndex[0]]
        return int("".join(num))

if __name__ == '__main__':
    so = Solution()
    num = 9973
    r = so.maximumSwap(num)
    print(r)
